package day4;

public class 单词搜索 {
	public int[] dx=new int[]{0,0,1,-1};
	public int[] dy=new int[]{1,-1,0,0};
	public boolean[][] visit;
	public int _m,_n;
	public boolean dfs(String[] board,String word,int i,int j,int pos){
		visit[i][j]=true;
		if(pos==word.length()){
			return true;
		}
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(x>=0&&x<_m&&y>=0&&y<_n&&visit[x][y]==false&&board[x].charAt(y)==word.charAt(pos)){
				if(dfs(board,word,x,y,pos+1)==true){
					return true;
				}
				//回溯
				visit[x][y]=false;
			}
		}
		return false;
	}
	public boolean exist (String[] board, String word) {
		// write code here
		_m=board.length;
		_n=board[0].length();
		for(int i=0;i<_m;i++){
			for(int j=0;j<_n;j++){
				if(board[i].charAt(j)==word.charAt((0))){
					visit=new boolean[_m][_n];
					if(dfs(board,word,i,j,1)==true){
						return true;
					}
				}
			}
		}
		return false;
	}
}
